#include <stdio.h>
#include <stdlib.h>
#define bool int
#define true 1
#define false 0
#define NULL ((void *)0)
#include <ctype.h>
static void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

static void insertSort(int *nums, int numsSize)
{
    int i, j, tmp;
    for (i = 1; i < numsSize; i++)
    {
        tmp = nums[i];
        for (j = i; j > 0 && tmp < nums[j - 1]; j--)
            nums[j] = nums[j - 1];
        nums[j] = tmp;
    }
}

static int median3(int *nums, int start, int end)
{
    int mid = (start + end) / 2;
    if (nums[start] > nums[mid])
    {
        swap(nums + start, nums + mid);
    }
    if (nums[mid] > nums[end])
    {
        swap(nums + mid, nums + end);
    }
    if (nums[start] > nums[mid])
    {
        swap(nums + start, nums + mid);
    }
    swap(nums + mid, nums + end - 1);

    return nums[end - 1];
}

static void qSort(int *nums, int start, int end)
{
    int tmp;
    int i, j;

    if (start + 3 < end)
    {
        tmp = median3(nums, start, end);
        i = start;
        j = end - 1;
        while (1)
        {
            while (nums[++i] < tmp)
                ;
            while (nums[--j] > tmp)
                ;
            if (i < j)
            {
                swap(nums + i, nums + j);
            }
            else
            {
                break;
            }
        }

        swap(nums + i, nums + end - 1);
        qSort(nums, start, i - 1);
        qSort(nums, i + 1, end);
    }
    else
    {
        insertSort(nums + start, end - start + 1);
    }
}

static void quickSort(int *nums, int numsSize)
{
    qSort(nums, 0, numsSize - 1);
}

static bool containDupAfterSort(int *nums, int numsSize)
{
    int i = 0;
    while (i < numsSize - 1)
    {
        if (nums[i] == nums[++i])
        {
            return true;
        }
    }
    return false;
}

static bool containsDuplicate(int *nums, int numsSize)
{
    if (nums == NULL || numsSize <= 1)
    {
        return false;
    }

    quickSort(nums, numsSize);
    return containDupAfterSort(nums, numsSize);
}

int main()
{
    int test[6] ={ 0,
        4,
        5,
        0,
        3,
        6 };
    printf("%s\n", containsDuplicate(test, 6) ? "true" : "false");
    for (int i = 0; i < 6; i++)
    {
        printf("%d,", test[i]);
    }
    printf("\n");

    exit(EXIT_SUCCESS);
}